QA644 : Guarding monotone art galleries with sliding cameras in linear time
Thesis > Central Library of Shahrood University > Mathematical Sciences > MSc > 2020
Authors:
[Author], Mehrdad Ghaznavi[Supervisor], Abolfazl Poureidi[Supervisor]
Abstarct: We study the problem of guarding an orthogonal art gallery with security cameras slid- ing back and forth along straight tracks. We show that if only vertical (alternatively, horizontal) tracks are allowed, then a solution minimizing the number of tracks can be found in polynomial time, and if both orientations are allowed, then a 2-approximation can be found in polynomial time for x-monotone galleries. A sliding camera in an orthogonal polygon P—that is, a polygon all of whose edges are axis-parallel—is a point guard g that travels back and forth along an axisparallel line segment sinside P. In the minimum sliding cameras (MSC) problem, the objective is to guard Pwith the minimum number of sliding cameras. We give a dynamic programming algorithm that solves the MSC problem exactly on monotone orthogonal polygons in O(n)time, improving the 2-approximation algorithm of Katz and Morgenstern (2011). Our results provide the first polynomial-time exact algorithms for the MSC problem on a non-trivial subclass of orthogonal polygons. Let P be an orthogonal polygon. Consider a sliding camera that travels back and forth along an orthogonal line segment s ⊂ P as its trajectory. The camera can see a point p ∈ P if there exists a point q ∈ s such that pq is a line segment normal to s that is completely contained in P. In this paper, we first settle the complexity of the minimum-length sliding cameras problem by showing that it is polynomial tractable even for orthogonal polygons with holes, answering a question posed by Katz and Morgenstern .
Keywords:
#Keywords: Art-gallery; mobile guards; perfect graphs; orthogonal polygons; lixnk distance. Keeping place: Central Library of Shahrood University
Visitor: